package _47

// 使用图算法, dfs/bfs 顶点个数-连通分量个数
func removeStones2(stones [][]int) int {
	n := len(stones)
	graph := make(map[int][]int)

	for i, p := range stones {
		for j, q := range stones {
			if p[0] == q[0] || p[1] == q[1] {
				graph[i] = append(graph[i], j)
			}
		}
	}

	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(v int) {
		vis[v] = true
		for _, p := range graph[v] {
			if !vis[p] {
				dfs(p)
			}
		}
	}

	cnt := 0

	for i, v := range vis {
		if !v {
			cnt++
			dfs(i)
		}
	}

	return n - cnt
}
